package leetcode.code0956;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution3 implements IDebug {

	int len;
	int ans;
	int[] rods;

	public int tallestBillboard(int[] rods) {
		len = rods.length;
		ans = 0;
		this.rods = rods;
		int max = Arrays.stream(rods).sum();
//		boolean[][][] dp = new boolean[len + 1][max + 1][max + 1];// 记忆化搜索用这个超内存
		Map<Integer, Map<Integer, Set<Integer>>> dp = new HashMap<>();
//		f(0, 0, 0, dp);// 超时，系统栈问题？
		Stack<int[]> stack = new Stack<>();
		stack.add(new int[] { 0, 0, 0 });
		while (!stack.isEmpty()) {
			int[] c = stack.pop();
			int i = c[0], a = c[1], b = c[2];
			if (a == b) {
				ans = Math.max(ans, a);
			}
			if (i == len || (dp.containsKey(i) && dp.get(i).containsKey(a) && dp.get(i).get(a).contains(b))) {
				continue;
			}
			dp.computeIfAbsent(i, k -> new HashMap<>()).computeIfAbsent(a, k -> new HashSet<>()).add(b);
			stack.add(new int[] { i + 1, a, b });
			stack.add(new int[] { i + 1, a + rods[i], b });
			stack.add(new int[] { i + 1, a, b + rods[i] });
		}
		return ans;
	}

	// 这个会超时，数据多的时候
	private void f(int i, int a, int b, Map<Integer, Map<Integer, Set<Integer>>> dp) {
		if (a == b) {
			ans = Math.max(ans, a);
		}
		if (i == len || (dp.containsKey(i) && dp.get(i).containsKey(a) && dp.get(i).get(a).contains(b))) {
			return;
		}
		dp.computeIfAbsent(i, k -> new HashMap<>()).computeIfAbsent(a, k -> new HashSet<>()).add(b);
		f(i + 1, a, b, dp);
		f(i + 1, a + rods[i], b, dp);
		f(i + 1, a, b + rods[i], dp);
	}

	@Override
	public void debug4() {
		H.compare(6, this
				.tallestBillboard(H.str2array3("[1,2,4,8,16,32,64,128,256,512,50,50,50,150,150,150,100,100,100,123]")));
//		H.compare(6, this.tallestBillboard(H.str2array3("[1,2,3,6]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
//		long ans = 0;
//		for (int i = 1; i < 20; i++) {
//			ans += Math.pow(2, i) * Math.pow(2, 20 - i);
//		}
//		System.out.println(ans);
	}

}
